const UnionFind = require('./dataStruct/unionFind').UnionFind;
const common = require('./base/common');

/**
 * 959. 由斜杠划分区域
 * 
 * @param {string[]} grid
 * @return {number}
 */
var regionsBySlashes = function(grid) {
    let N = grid.length;
    let u = new UnionFind(4 * N * N);

    for(let i=0; i < N; ++i) {
        for(let j=0; j < N; ++j) {
            let index = 4 * (N * i + j);
            if(grid[i][j] == " ") {
                u.union(index, index + 1);
                u.union(index + 1, index + 2);
                u.union(index + 2, index + 3);
            } else if(grid[i][j] == "/") {
                u.union(index, index + 3);
                u.union(index + 1, index + 2);
            } else if(grid[i][j] == "\\") {
                u.union(index, index + 1);
                u.union(index + 2, index + 3);
            }

            if(j - 1 >= 0) {
                u.union(index + 3, index - 3);
            }
            if(i - 1 >= 0) {
                u.union(index, index - 4 * N + 2);
            }
        }
    }

    let set = new Set();
    for(let i=0; i < 4 * N * N; ++i) {
        set.add(u.find(i));
    }

    return set.size;
};

common.testing([
    ["///","/ /", " / "],
    ["//", "/ "]
], [4, 3])((x) => regionsBySlashes(x));